#include "iostream"
#include "vector"

using namespace std;

class Solution215 {
private:
    int participation(vector<int> &i, int start, int end) {
        int pivot = i[start];
        while (start < end) {
            while (start < end && pivot <= i[end])end--;
            i[start] = i[end];
            while (start < end && pivot >= i[start])start++;
            i[end] = i[start];
        }
        i[start] = pivot;
        return start;
    }

public:
    int findKthLargest(vector<int> &nums, int k) {
        int start = 0;
        int end = nums.size() - 1;
        int pivot = 0;
        while (start < end) {
            pivot = participation(nums, start, end);
            if (pivot == nums.size() - k)return nums[pivot];
            if (pivot > nums.size() - k) end = pivot - 1;//左边找
            if (pivot < nums.size() - k) start = pivot + 1; //右边找
        }
        return nums[start];
    }
};